/**
 * @file     reoderList.js
 * @brief    [143. 重排链表](https://leetcode-cn.com/problems/reorder-list/)
 * @author   Zhu
 * @date     2022-03-17 16:17
 */

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

/**
 * 利用数组 + 双指针，重建链表
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
    const list = [];
    let cur = head;
    while (cur) {
        list.push(cur);
        cur = cur.next;
    }

    let i = 0,
        j = list.length - 1;
    while (i < j) {
        list[i].next = list[j];
        i++;
        list[j].next = list[i];
        j--;
    }

    list[i].next = null;
};

/**
 * 先折半；再倒序后半段；最后合并
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
    // 偶数取前一个
    function getMiddle(head) {
        let fast = head;
        while (fast && fast.next && fast.next.next) {
            fast = fast.next.next;
            head = head.next;
        }
        return head;
    }
    // 倒序
    function reverseList(head) {
        let pre = null;
        while (head) {
            let tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }

    const mid = getMiddle(head);
    let tail = mid.next;
    mid.next = null;
    tail = reverseList(tail);

    // 交替合并
    while (head && tail) {
        const nextHead = head.next;
        const nextTail = tail.next;
        head.next = tail;
        tail.next = nextHead;
        head = nextHead;
        tail = nextTail;
    }
};
